from typing import List


class Solution:
    def ringGame(self, challenge: List[int]) -> int:
        # 最终结果一定大于最大位
        max_val = max(challenge)
        max_bit = max_val.bit_length()  # 最大位
        bit_val = 1 << (max_bit - 1)  # 最大位的值
        res_val = bit_val * 2 - 1  # 必然可以匹配其他一切值的值
        # print("最大值:", max_val, "最大位:", max_bit, "最大位的值:", bit_val)

        # ----- 将小于最大位的值的数合并 -----
        # 新数组：[当前值,当前左右合并小数之后的值]
        clear1 = []
        less_val = 0  # 当前两个大值之间间隔的小值的OR
        for num in challenge:
            if num < bit_val:
                less_val |= num
            else:
                if len(clear1) > 0:
                    clear1[-1][1] |= less_val
                if less_val > 0:
                    clear1.append([bit_val, bit_val | less_val])
                clear1.append([num, num | less_val])
                less_val = 0
        clear1[-1][1] |= less_val

        print("第1次整理结果:", clear1)

        if len(clear1) == 1:
            return clear1[0][0]

        # ----- 处理双向可合并的情况 -----
        clear2 = []
        for v2, m2 in clear1:
            if not clear2:
                clear2.append([v2, m2])
                continue

            v1, m1 = clear2[-1]

            if m1 >= v2 and m2 >= v1:
                clear2[-1][0] = min(v1, v2)
                clear2[-1][1] = max(m1, m2)
            else:
                clear2.append([v2, m2])

        print("第2次整理结果:", clear2)

        if len(clear2) == 1:
            return clear2[0][0]

        # ----- 处理右侧无损合并左侧的情况 -----
        clear3 = []
        for v2, m2 in clear2:
            if not clear3:
                clear3.append([v2, m2])
                continue

            v1, m1 = clear2[-1]

            if v2 <= v1 and m2 >= m1:
                clear2[-1][0] = min(v1, v2)
                clear2[-1][1] = max(m1, m2)
            else:
                clear2.append([v2, m2])

        print("第3次整理结果:", clear2)

        if len(clear2) == 1:
            return clear2[0][0]


if __name__ == "__main__":
    print(Solution().ringGame(challenge=[5, 4, 6, 2, 7]))  # 4
    print(Solution().ringGame(challenge=[12, 7, 11, 3, 9]))  # 8
    print(Solution().ringGame(challenge=[1, 1, 1]))  # 1

    # 自制用例
    print(Solution().ringGame(challenge=[15, 6, 15, 1]))  # 15
    print(Solution().ringGame(challenge=[5, 7, 11, 13, 14, 15]))  # 8
    print(Solution().ringGame(challenge=[15, 11, 13, 15]))  # 11
